/*
 * @lc app=leetcode.cn id=886 lang=typescript
 *
 * [886] 可能的二分法
 */

// @lc code=start
function possibleBipartition(n: number, dislikes: number[][]): boolean {
  // 值为0表示未标记，1和2分别为不同的组
  const colors: number[] = new Array(n + 1).fill(0);
  // 当前索引保存的是不喜欢的人列表
  const graph: number[][] = new Array(n + 1).fill(0).map((_) => []);
  // 建模
  for (const [first, second] of dislikes) {
    graph[first].push(second);
    graph[second].push(first);
  }

  const dfs = (
    currNode: number,
    currColor: number,
    colors: number[],
    graph: number[][]
  ): boolean => {
    // 标记
    colors[currNode] = currColor;
    for (const nextNode of graph[currNode]) {
      // 下一个节点标记过，但是和当前节点颜色相同，有冲突
      if (colors[nextNode] !== 0 && colors[nextNode] === colors[currNode]) {
        return false;
      }
      // 下一个节点未标记，开始标记，看看是否有冲突
      if (colors[nextNode] === 0 && !dfs(nextNode, 3 ^ currColor, colors, graph)) {
        return false;
      }
    }
    return true;
  };

  for (let i = 1; i <= n; i++) {
    // 当前节点标记过，跳过
    if (colors[i] !== 0) continue;
    if (!dfs(i, 1, colors, graph)) return false;
  }

  return true;
}
// @lc code=end
